//
// Created by yewei on 2025/4/29.
//
#define LEN 100

int Top_Down_Cut_Rod(int p[], int n) {
    int r = 0;
    int i;
    if (n == 0) {
        return 0;
    }
    for (i = 1; i <= n; i++) { //1
        int tmp = p[i] + Top_Down_Cut_Rod(p, n - i);
        r = (r >= tmp) ? r : tmp;
    }
    return r;
}

int Bottom_Up_Cut_Rod(int p[], int n) {
    int r[LEN] = {0};
    int temp = 0;
    int i, j;
    for (j = 1; j <= n; j++) {
        temp = 0;
        for (i = 1; i <= j; i++) { //2
            temp = (temp >= (r[i] + r[j - i])) ? temp : (r[i] + r[j - i]); //3
        }
        r[j] = (temp > p[j]) ? temp : p[j]; //4
    }
    return r[n];
}